/**
 * describe:
 *
 * @author chaP
 * @date 2019/04/11
 */
package CodingTest.AC20190410;

import java.util.ArrayList;
import java.util.List;

public class permute {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<>();
        helper(nums,result,list);
        return result;
}
    public void helper(int[] nums,List<List<Integer>> result,List<Integer> list){
        if(list.size() == nums.length)
            result.add(new ArrayList<Integer>(list));
        for(int i = 0;i<nums.length;i++){
            if(list.contains(nums[i])) continue;
            list.add(nums[i]);
            helper(nums,result,list);
            list.remove(list.size()-1);
        }
    }
    //方法二：
    public List<List<Integer>> perm(int[] nums){
        List<List<Integer>> res = new ArrayList<>();
        dfs(res,nums,0);
        return res;
    }
    public void dfs(List<List<Integer>> res,int[] nums,int from){
        if(from == nums.length){
            List<Integer> tmp = new ArrayList();
            for(int i = 0;i<nums.length;i++){
                tmp.add(nums[i]);
            }
            res.add(tmp);
        }else{
            for(int j = from;j<nums.length;j++){
                swap(nums,from,j);
                dfs(res,nums,from+1);
                swap(nums,j,from);
            }
        }
    }
    public void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    public static void main(String[] args) {
        permute sb = new permute();
        int [] nums = {1,2,3};
        System.out.println(sb.permute(nums));
    }
}
